package com.mashibing.class08;

import java.util.Stack;

/**
 * 快排的流程:
 * arr[]={3,6,9,7,6,2,8,2,7}
 * 以数组的最后一个元素(7)作为基准, 经历一次排序之后, <=7的都放在左边, >7的都放在右边
 * 设计一个区域, 这个区域叫做小于或等于7, 拿最后一个数作划分, 从数组0开始
 * 小于或等于区 初始化状态是空的.(初始索引是-1)
 * 1) 当前数<=p(最后一个元素7), 当前数和小于等于区的下一个数作交换,
 * 然后小于等于区右扩,当前数跳下一个.
 * 2) 当前数 >p(最后一个元素7),当前数直接跳下一个.
 */
public class Code03_PartitionAndQuickSort {

    public static void splitNum(int[] arr){
        int lessEqualR = -1; // 小于或等于区域的右边界初始化为 -1
        int index = 0;
        int mostR = arr.length-1; // 划分值是arr最右侧的数
        while (index<arr.length){
            if (arr[index] <= arr[mostR]){
//                swap(arr,lessEqualR+1,index);
//                lessEqualR++; // 小于或者等于区域右扩
//                index++; // 当前数跳下一个
                swap(arr,++lessEqualR,index++);
            }else {
                index++;// 当前数直接跳下一个
            }
        }
    }

    // 升级版本
    /**
     * arr[]={3,6,9,7,6,2,8,2,7}
     * 在数组中拿最后一个元素(7)做划分, 该元素用p表示
     * 将小于7的放左边,大于7的放在右边 等于7的放中间.
     * 小于区域 放在-1位置 大于区域的界限把最末尾元素罩上。
     * 从第0号元素开始遍历
     * 1) 当前数 < p, 当前数 和 小于区下一个数作交换, 小于区域往右扩, 当前数跳下一个.
     * 2) 当前数 > p，当前数 和 大于区前一个数作交换, 大于区域往左扩, 当前数不动.
     * 3) 当前数 ==p, 当前数直接跳.
     * 4) 当前数 和 大于区域的左边界撞上的时候, 本次遍历结束.
     */
    public static void splitNum2(int[] arr){
        int N = arr.length;
        int lessR = -1; // 小于或等于区域的右边界初始化为 -1
        int moreL = N-1;
        int index = 0;
        while (index<moreL){
            if (arr[index] < arr[N-1]){
                swap(arr,++lessR,index++);
            } else if (arr[index] > arr[N-1]) {
                swap(arr,--moreL,index);
            } else {
                index++;// 当前数直接跳下一个
            }
        }
        swap(arr,moreL,N-1);
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    // 在arr[L...R]范围上,拿arr[R]做划分值
    // L....R < = >
    public static int[] partition(int[] arr,int L,int R){
        int lessR = L-1; // 小于区域的左边界
        int moreL = R;  // 大于区域的右边界
        int index = L;

        while (index<moreL){
            if (arr[index] < arr[R]){
                swap(arr,++lessR,index++);
            } else if (arr[index] > arr[R-1]) {
                swap(arr,--moreL,index);
            } else {
                index++;// 当前数直接跳下一个
            }
        }
        swap(arr,moreL,R); // 要把最后一个元素归位到等于区域.
        return new int[]{lessR+1,moreL};
    }

    public static void quickSort(int[] arr){
        if (arr==null||arr.length<2){
            return ;
        }
        process(arr,0, arr.length-1);
    }

    public static void process(int[] arr,int L,int R){
        if (L >= R){
            return;
        }
        // L < R
        int[] equalE = partition(arr,L,R);
        // equalE[0]  等于区域的第一个数
        // equalE[1]  等于区域的第一个数
        process(arr,L,equalE[0]-1);
        process(arr,equalE[1]+1,R);

    }

    // 定义一个任务类
    public static class Job{
        public int L;
        public int R;
        public Job(int left,int right){
            L = left;
            R = right;
        }
    }

    // 非递归版本
    public static void quickSort2(int[] arr){
        if (arr==null||arr.length<2){
            return ;
        }
        Stack<Job> stack = new Stack<>();
        stack.push(new Job(0,arr.length-1));
        while (!stack.isEmpty()){
            Job cur = stack.pop();
            int[] equals = partition(arr, cur.L, cur.R);
            if (equals[0]> cur.L){ // 有小于区域
                stack.push(new Job(cur.L, equals[0]-1));
            }
            if (equals[1]< cur.R){
                stack.push(new Job(equals[1]+1,cur.R));
            }
        }
    }


    public static void main(String[] args) {
        int arr[]={3,6,9,7,6,2,8,2,7,3};
     //   splitNum2(arr);
        quickSort2(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}
